This invention is related to the field of design automation, and more particularly, to a method for reducing the size of RC parasitics of interconnect networks in an integrated circuit (IC) in order to reduce circuit analysis time.
During final timing verification of integrated circuits (ICs), it is crucial to rigorously account for all the RC parasitics in the interconnect networks that link the various transistors in the IC, a known cause of significant delays in the interconnects. Emerging newer and more complex technologies continue to shrink feature sizes, leading to increasing the dominance of the interconnect delays. At present, a circuit extraction tool is used to generate these RC parasitics from a description of the layout of the interconnect. Unfortunately, this creates extremely large RC networks with a wide range of dynamic time constants that can choke downstream detailed circuit analysis tools in the following manner: (1) the size of RC networks is very large, resulting in a significant increase in run-time due to the large size of the circuit matrices; and (2) the wide range of dynamic time constants causes the analysis tools to take extremely small numerical time-steps, resulting in a further increase in the run-time.
Thus, a rigorous accounting of metal R and C is highly advantageous, particularly in deep sub-micron technologies, because of the large delays attributable to these interconnects. It is also desirable to reduce (or crunch down) the large RC networks generated by circuit extraction tools by reducing the size and narrowing the range of dynamic time constants. It should be noted that the run-time advantage of crunching resistor networks in a more compact form applies at each time step of each simulation performed by the detailed circuit analysis tool. This is highly significant because each of these simulations are typically run multiple times during circuit optimization, and the same compressed RC network continues to be reused for all the iterations.
An integrated circuit can be represented by a collection of transistors with the terminals interconnected by nets. After completing the layout, each net is electrically modeled as an RC network of nodes and elements. The elements of the network are resistors (Rs) and capacitors (Cs). Nodes connecting transistor terminals are referred to boundary nodes, while the remaining ones are referred to as internal nodes of the RC network.
Prior art techniques select only internal nodes for elimination based on its nodal time constant defined by:                     τ        =                  C          γ                                    (        1        )            
where C is the grounded capacitance of the node and xcex3 is the total conductance (i.e., the inverse of the resistance) connected to the node. For example, for node X shown in FIG. 1, the grounded capacitance and the total conductance are given by:
C=CXxe2x80x83xe2x80x83(2) 
xcex3=G1+G2+G3+G4xe2x80x83xe2x80x83(3) 
Prior art techniques eliminate an internal node when its nodal time constant xcfx84 is smaller than a predetermined threshold xcfx84max. When a node is selected for elimination, the grounded capacitance of the node and all the resistors connected to the node are distributed to neighboring nodes using the following formula:                               C          i                =                              C            X                    ⁢                                    G              i                        γ                                              (        4        )                                          G          ij                =                                            G              i                        ⁢                          G              j                                γ                                    (        5        )            
where i and j represent the index of a pair of neighboring nodes of the node X being eliminated, Ci is the additional capacitance to be added to the existing grounded capacitance at node i, and Gij is a (possibly new) conductance introduced between nodes i and j. FIG. 2 is an illustration of the node elimination process for node X in the example given in FIG. 1.
The total capacitance of the RC network remains the same after the elimination of an internal node:                                                                                           ∑                  i                                ⁢                                  C                  i                                            =                                                C                  X                                γ                                                                                                          ∑                  i                                ⁢                                  G                  i                                            =                              C                X                                                                        (        6        )            
Moreover, it can be shown that the Elmore delays at all boundary nodes are preserved by the elimination process. (Elmore""s delay is the first time-moment of the impulse response at a sink. The response at a sink due to an arbitrary input waveform is simply the convolution of the impulse response with the input waveform). This is highly regarded property of the RC reduction process.
Whenever a node is eliminated, the node count is reduced by 1, although the number of resistors may actually increase. For instance, in the example shown in FIG. 2, there are four resistors prior to elimination, but six thereafter. Increasing the total number of resistors is not desirable since the circuit matrices become denser. In general, for a node with k neighbors that already has m resistors among its neighbors, the fill-in count, or the total number of new resistors created after its elimination, is given by:                     ξ        =                                            k              ⁡                              (                                  k                  -                  1                                )                                      2                    -          m          -          k                                    (        7        )            
Internal node elimination is generally restricted to only those nodes that have a fill-in count of 0 or less to preserve the sparsity of the reduced RC network, since the total number of resistors cannot increase.
The problem with conventional techniques is that they apply only to the elimination of internal nodes, and not to boundary nodes of the RC networks. An example of the latter is shown in FIG. 3, where node X is connected to the gate terminal of a transistor external to the RC network. Even if node X had a small ( less than xcfx84max) time constant, prior art methods would not eliminate it because by eliminating node X, the gate terminal of the transistor shown in FIG. 3 would have to be split up and distributed among the neighboring nodes (1, 2, 3, and 4), resulting in a circuit that is not equivalent to the original one.
In transistor-level static timing analysis, circuits which contain large RC networks with many boundary nodes and a wide range (over seven orders of magnitude) of time constants are routinely encountered. Since algorithms in the prior art only eliminate internal nodes, their quality is limited since there usually remains a large number of boundary nodes with very small time constants (several orders of magnitude less than the Elmore delay).
It is, therefore, an object of the invention to reduce large parasitic RC networks in the interconnect of an integrated circuit design, preferably after having applied internal node elimination techniques (or any other RC reduction technique).
It is another object to speed up the analysis of the resulting RC network without a significant loss of accuracy.
It is another object to provide the user with a smooth size-versus-accuracy tradeoff such that as the accuracy requirement is lowered, the size of the RC network approaches the lower limit of each interconnect having no resistors. The speed of the circuit analysis tools is the fastest at this extreme limit.
In a first aspect of the invention, there is provided a method for allowing further reduction of parasitic RC networks after applying conventional internal node elimination techniques.
The present inventive method further reduces (beyond only eliminating internal nodes) RC networks by shorting certain resistors connected to the boundary nodes, and adjusting the value of neighboring resistors to compensate for the errors introduced by the shorting. This additional reduction of the RC networks greatly improves the performance of downstream analysis tools, such as circuit simulators, without a significant loss of accuracy.
A resistor is selected as a candidate for shorting if the accumulated delay error at either end is less than a predetermined threshold. This threshold is a fraction (e.g., {fraction (1/10)}) of the time-constant threshold chosen for the internal node elimination conventional technique in order to limit the growth of the accumulated delay error. After shorting the resistor, the accumulated delay error at the merged node is updated and values of downstream resistors are changed to preserve the delay at downstream nodes. An important aspect of the invention is the simplicity of the formula used to change the downstream resistor value, namely, the product of the value of the resistor shorted and the ratio of the cumulative down stream capacitors of the two ends of the resistor whose value is being changed. This particular choice of updating the downstream resistor values minimizes the absolute-value of the delay errors at every node due to shorting of the selected resistor.
In still another object of the invention, there is provided a method for reducing the size of RC parasitics in an interconnect network of an integrated circuit (IC), the IC being formed as a collection of transistors, each having its terminals interconnected by nets, each of the nets modeled by nodes and elements, the elements modeled as resistors (R) and capacitors (C), the nodes attached to transistor terminals labeled as boundary nodes while the remaining nodes are labeled as internal nodes, the method including the steps of: a) selecting a net from the collection of nets; b) reducing the size of the RC network of the selected net by eliminating the internal nodes having a time-constant below a predetermined threshold and a fill-in count contained within a pre-specified limit; c) iteratively shorting a resistor connected to a boundary node, wherein the accumulated delay error at the boundary node after shorting is less than a fraction of the predetermined threshold; d) updating the values of the resistors adjoining the shorted resistor, wherein no additional delay error is generated in the remaining nodes due to shorting the resistor; and repeating steps c) and d) until no boundary nodes are found in the selected RC network meeting the predetermined threshold.